import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

import Utiles.Punkt;

/*
131,673,234,103,18
201,96,342,965,150
630,803,746,422,111
537,699,497,121,956
805,732,524,37,331
 */


public class Main_083 {
	
	/**
	 * @param args
	 * @throws FileNotFoundException 
	 */
	
	static int size = 80;
	static int[][] matrix = new int[size][size];
	static boolean[][] visited = new boolean[size][size];
	
	
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub					
		Scanner sc = new Scanner(new File("prob83.txt"));
		
		String line;
		String[] zw;
		int x = 0;
		while(sc.hasNextLine()){
			line = sc.nextLine();
			zw = line.split(",");
			for(int i = 0; i < zw.length; ++i){
				matrix[x][i] = Integer.parseInt(zw[i]);
				visited[x][i] = false;
			}
			++x;
		}
		
		sc.close();
		
		/*for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				System.out.print(matrix[i][j]+"("+visited[i][j]+")\t");
			}
			System.out.print("\n");
		}*/
		
		dijk();
		
		System.out.println("Fertig!");		
	}
	
	public static void dijk(){
		ArrayList<Punkt> pu = new ArrayList<Punkt>();
		Punkt p = new Punkt(0,0,matrix[0][0], null);
		pu.add(p);	
		
		int min, pos;
		int x,y;
		while(p.x != (size-1) || p.y != (size-1)){
			min = getLowest(pu);
			p = pu.get(min);
			pu.remove(min);
			visited[p.x][p.y] = true; 
			if(p.x < (size-1) && visited[p.x+1][p.y] == false){
				pos = isIn(pu, p.x+1, p.y);
				if(pos < 0){
					pu.add(new Punkt(p.x+1, p.y, p.sum+matrix[p.x+1][p.y], p));
				}else{
					min = pu.get(pos).sum;
					if(p.sum+matrix[p.x+1][p.y] < min){
						pu.get(pos).sum = p.sum+matrix[p.x+1][p.y];
						pu.get(pos).prev = p;
					}
				}
			}
			
			if(p.x > 0 && visited[p.x-1][p.y] == false){
				pos = isIn(pu, p.x-1, p.y);
				if(pos < 0){
					pu.add(new Punkt(p.x-1, p.y, p.sum+matrix[p.x-1][p.y], p));
				}else{
					min = pu.get(pos).sum;
					if(p.sum+matrix[p.x-1][p.y] < min){
						pu.get(pos).sum = p.sum+matrix[p.x-1][p.y];
						pu.get(pos).prev = p;
					}
				}
			}
			
			if(p.y < (size-1) && visited[p.x][p.y+1] == false){
				pos = isIn(pu, p.x, p.y+1);
				if(pos < 0){
					pu.add(new Punkt(p.x, p.y+1, p.sum+matrix[p.x][p.y+1], p));
				}else{
					min = pu.get(pos).sum;
					if(p.sum+matrix[p.x][p.y+1] < min){
						pu.get(pos).sum = p.sum+matrix[p.x][p.y+1];
						pu.get(pos).prev = p;
					}
				}
			}
			
			if(p.y > 0 && visited[p.x][p.y-1] == false){
				pos = isIn(pu, p.x, p.y-1);
				if(pos < 0){
					pu.add(new Punkt(p.x, p.y-1, p.sum+matrix[p.x][p.y-1], p));
				}else{
					min = pu.get(pos).sum;
					if(p.sum+matrix[p.x][p.y-1] < min){
						pu.get(pos).sum = p.sum+matrix[p.x][p.y-1];
						pu.get(pos).prev = p;
					}
				}
			}
			
			
			//System.out.println(p+" -> "+matrix[p.x][p.y]);
			
		}
		System.out.println(p.sum);
		//System.out.println(pu);
		/*for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				System.out.print(matrix[i][j]+"("+visited[i][j]+")\t");
			}
			System.out.print("\n");
		}*/
	}
	
	public static int isIn(ArrayList<Punkt> pu, int x, int y){
		for (int i = 0; i < pu.size(); i++) {
			if(pu.get(i).x == x && pu.get(i).y == y){
				return i;
			}
		}
		return -1;
	}
	
	public static int getLowest(ArrayList<Punkt> pu){
		int min = 0;
		int minINdex = 0;
		for (int i = 0; i < pu.size(); i++) {
			if(i != 0){
				if(min > pu.get(i).sum){
					min = pu.get(i).sum;
					minINdex= i;
				}
			}else{
				min = pu.get(i).sum;
			}
		}
		return minINdex;
	}
}
